#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_NUM_OF_PROCESS  32
#define MAX_NUM_OF_ROUNDS   10
#define TRUE                1
#define FALSE               0

static int num_of_process = 4;
static int num_of_rounds;

enum Role{
    winner,
    loser,
    bye,
    champion,
    dropout,
    unused
};

struct Round {
    enum Role role;
    int *opponent;
    int flag;
};

static struct Round rounds[MAX_NUM_OF_PROCESS][MAX_NUM_OF_ROUNDS];
static int ompsense = TRUE;
static int round = 1;
#pragma omp threadprivate(ompsense, round)

void init_tournament_barrier_omp(int nump)
{
    if (nump != 0) 
        num_of_process = nump;
    int i, k, two_k, two_k_1;
    
    if (num_of_process > MAX_NUM_OF_PROCESS) 
        num_of_process = MAX_NUM_OF_PROCESS;
    // calculate num of rounds
    // wonder why log() is not working
    i = 1;
    num_of_rounds = 1;
    while (i < num_of_process) {
        i <<= 1;
        ++num_of_rounds;
    }

    for (i=0; i<num_of_process; ++i) {
        for (k=0; k<num_of_rounds; ++k) {
            
            two_k = (1<<k); // 2^k
            two_k_1 = (two_k>>1); // 2^(k-1)

            // Init flag
            rounds[i][k].flag = FALSE;
            
            // Start init roles
            if (k == 0)
                // dropout if k = 0
                rounds[i][k].role = dropout;
            else { // k > 0
                if (i == 0 && two_k >= num_of_process)
                    // champion if k > 0, i = 0, and 2^k >= P
                    rounds[i][k].role = champion;
                else if (i % two_k == two_k_1)
                    // loser if k > 0 and i mod 2^k = 2^(k-1)
                    rounds[i][k].role = loser;
                else if (i % two_k == 0) {
                    if (i + two_k_1 >= num_of_process)
                        // bye if k > 0, i mod 2^k = 0, and i + 2^(k-1) >= P
                        rounds[i][k].role = bye;
                    else if (two_k < num_of_process)
                        // winner if k > 0, i mod 2^k = 0, i + 2^(k-1) < P, and 2^k < P
                        rounds[i][k].role = winner;
                    else rounds[i][k].role = unused; // otherwise
                }
                else rounds[i][k].role = unused; // otherwise
            } // else k > 0
            // End init roles
            
            // Start init opponent
            if (rounds[i][k].role == loser) 
                rounds[i][k].opponent = &rounds[i-two_k_1][k].flag;
            if (rounds[i][k].role == winner || rounds[i][k].role == champion)
                rounds[i][k].opponent = &rounds[i+two_k_1][k].flag;
            // End init opponent
        }
    }
#ifdef DEBUG
    for (i=0; i<num_of_rounds; ++i) {
        printf("ROUND: %d\n", i);
        for (k=0; k<num_of_process; ++k) {
            printf("p %d r: %d\t", k, rounds[k][i].role);
        }
        printf("\n");
    }
#endif
}

void tournament_barrier_omp()
{
    int vpid = omp_get_thread_num();
    //int sense = TRUE; // threadprivate is not supported on Mac GCC 4.2

    // arrival
    do {
        switch (rounds[vpid][round].role) {
            case loser:
                *rounds[vpid][round].opponent = ompsense;
                while (rounds[vpid][round].flag != ompsense);
                goto next; 
                break;
            case winner:
                while (rounds[vpid][round].flag != ompsense);
                break;
            case bye:
                // do nothing
                break;
            case champion:
                while (rounds[vpid][round].flag != ompsense);
                *rounds[vpid][round].opponent = ompsense;
                goto next;
                break;
            default:
                break;
        } // switch
        ++round;
    } while (1);
next:;
}

void release_barrier_omp() 
{
    int vpid = omp_get_thread_num();
    // wakeup
    do {
        --round;
        switch (rounds[vpid][round].role) {
            case loser: case champion:
                // throw exception
                exit(1);
            case bye:
                // do nothing
                break;
            case winner:
                *rounds[vpid][round].opponent = ompsense;
                break;
            case dropout:
                goto out;
                break;
            default:
                break;
        }
    } while (1);
out:
    ompsense = 1 - ompsense;
}

void omp_tournament_barrier()
{
    tournament_barrier_omp();
    release_barrier_omp();
}


